/**
 *
 * @file
 *		heap_ludmila
 *
 * @brief
 *		Heap implementation by ludmila
 *
 * Internal data structure description
 *
 * We store information in internal data structure
 * heap_ludmila::map<void*, mem_block> mem_map where
 * mem_block is a struct of size_t and tag
 * In mem_map we store information about allocated chunks: pointer on the chunk, 
 * size of chunk and tag that is associted with this chunk
 * Also we have a pointer to the heap void* heap_address.
 *
 * Algorithm and functions description
 *
 * heap_ludmila::heap_ludmila( size_t total, alloc_flags flag )
 * In constructor we allocate the global piece of memory for our storage. If memory 
 * wasn't allocated we set the total_limit field to 0 so then we use heap we should
 * check this field after calling constructor.
 * If alloc_debug flag set we poison memory with POISON_FREE.
 *
 * heap_ludmila::~heap_ludmila()
 * If storage is empty and heap_address pointer isn't NULL(it means that constructor 
 * failed to allocate memory) the free our heap
 *
 * void* heap_ludmila::alloc( size_t sz, unsigned int tag )
 * If we have enough memory to allocate we call find_block function that goes through mem_map
 * and tries to find a piece of memory with the size we need to allocate. Here we use the fact
 * that keys in stl::map are stored in increasing order. If block was found we insert
 * new pair in mem_map and return a pointer to the client application else we tells
 * the client that memory can't be allocated due to fragmentation.
 * If alloc_debug flag set we poison memory with POISON_ALLOC.
 * 
 * void* heap_ludmila::find_block(unsigned int size)
 * Find_block goes through mem_map. If it finds a dirty block it asks mem_map
 * how long is the piece that begins from this block and increase ptr. If it finds a piece of
 * free memory with appropriate size it returns a pointer to it.
 *
 * void heap_ludmila::free(void *ptr)
 * Checks if the piece is in mem_map. If true it calls void
 * heap_ludmila::free_base(void *ptr, map<void*, mem_block>::iterator iter) else it tells
 * the client that pointer is wrong or the memory wasn't allocated.
 *
 * void heap_ludmila::free_all(unsigned int tag)
 * Checks if using tags is enabled and if true goes through mem_map and calls free_base()
 * for each piece with the same tag else tells the client that tags are disabled
 *
 * void heap_ludmila::free_base(void *ptr, map<void*, mem_block>::iterator iter)
 * Deletes mem_map[iter] from mem_map
 * If alloc_debug flag set we poison memory with POISON_FREE
 *
 * void heap_ludmila::print_bit_map()
 * Simple void to print bit_arr. Good for visualing rather small areas( < 1Mb ). In our class we don't
 * actually have bitmap anymore but this functionality maybe usefull when debugging so we performed it
 * via going through mem_map
 *
 * void heap_ludmila::print_allocation_space()
 * Full dump of heap including allocated pieces with their size and tag and free blocks
 *
 * void heap_ludmila::statistics()
 * It shows how much memory is allocated for every tag.
 *
 */

#include "../../api/heap.h"
#include "heap_ludmila.h"
#include <vector>
#include <map>
using namespace std;

#define Err printf

#ifndef _DEBUG
#define printf
#endif

//If the memory isn't allocated total_limit field is set 0

heap_ludmila::heap_ludmila( size_t total, alloc_flags flag ) 
	: heap876(total, flag, "ludmila"), alloc_sz(0)
{
	total = ((total + block_size - 1) / block_size) * block_size;
	this->total_limit = total;
	heap_address = (void*) malloc(total);
	if (total == 0)
	{
		throw bad_alloc("Size of allocation pool mustn't be null\n");
		return;
	}
	if (heap_address == NULL)
	{
		this->total_limit = 0;
		throw bad_alloc("Can't allocate memory in system. Please try again later\n");
	} else {
		mutex = CreateMutex(NULL, FALSE, NULL);
		//this->total_limit = total;
		end_of_heap = (char*)(heap_address) + (total_limit / block_size) * block_size;
		if (this->flag & heap876::alloc_debug)
		{
			memset(heap_address, POISON_FREE, this->total_limit);
		}
	}
}

void heap_ludmila::print_bit_map()
{
	map<void*, mem_block>::iterator iter;
	void* ptr = heap_address;
	WaitForSingleObject(mutex, INFINITE);
	while ((char*)ptr < (char*)heap_address + total_limit)
	{
		iter = mem_map.find(ptr);
		if (iter != mem_map.end()) {
			int i;
			for (i = 0; i < (iter->second.size - 1 + block_size) / block_size; i++)
			{
				printf("1");
			}
			ptr = (void*)((char*)ptr + block_size * ((iter->second.size - 1 + block_size) / block_size));
		} else {
			printf("0");
			ptr = (void*)((char*)ptr + block_size);
		}
	}
	ReleaseMutex(mutex);
	printf("\n");
}

void heap_ludmila::print_allocation_space()
{
	map<void*, mem_block>::iterator iter;
	void* ptr = heap_address;
	WaitForSingleObject(mutex, INFINITE);
	while ((char*)ptr < (char*)heap_address + total_limit)
	{
		iter = mem_map.find(ptr);
		if (iter != mem_map.end()) {
			printf("Allocated block, address %p, size %p, tag %d \n", iter->first, iter->second.size, iter->second.tag);
			ptr = (void*)((char*)ptr + block_size * ((iter->second.size - 1 + block_size) / block_size));
		} else {
			printf("Free block\n");
			ptr = (void*)((char*)ptr + block_size);
		}
	}
	ReleaseMutex(mutex);
	printf("\n");
}

void heap_ludmila::statistics()
{
	map<void*, mem_block>::iterator iter;
	map<unsigned int, unsigned int> list; // list of tags and size of memory associted with tag
	map<unsigned int, size_t>::iterator l_iter;
	//WaitForSingleObject(mutex, INFINITE);
	for (iter = mem_map.begin(); iter != mem_map.end(); iter++)
	{
		l_iter = list.find(iter->second.tag);
		if (l_iter == list.end())
		{
			unsigned int tag = iter->second.tag;
			size_t size = iter->second.size;
			list.insert(std::make_pair(tag, size));
		} else {
			l_iter->second = l_iter->second + iter->second.size;
		}
	}
	//ReleaseMutex(mutex);
	size_t tmp_alloc_sz = alloc_sz;
	for (l_iter = list.begin(); l_iter != list.end(); l_iter++)
	{
		int tag = l_iter->first;
		int size = l_iter->second;
		float percent = ((float)size / (float)total_limit) * 100;
		if (!(this->flag & heap876::alloc_tagged))
		{ 
			printf("Allocated size %d, percents %d%\n", size, (int)percent);
		} else {
			printf("Tag %d, allocated size %d, percents %d %\n", tag, size, (int)percent);
		} 
	}
	printf("Total allocated %d, percents %d %\n", tmp_alloc_sz, (int)(((float)tmp_alloc_sz / (float)total_limit) * 100));
}

int heap_ludmila::check_poison(void* ptr, size_t size)
{
	if (this->flag & heap876::alloc_debug)
	{
		WaitForSingleObject(mutex, INFINITE);
		for (unsigned int j = 0; j < (size - 1 + sizeof(int)) / sizeof(int); j++)
		{
			if (*((int*)((char*)ptr + j * sizeof(int))) != POISON_FREE) {
				printf("Poison error\n");
				ReleaseMutex(mutex);
				return 0;
			}
		}
		ReleaseMutex(mutex);
		return 1;
	} else {
		return 1;
	}
}

void* heap_ludmila::find_block(size_t size) // size align to block_size
{
	map<void*, mem_block>::iterator iter;
	map<void*, mem_block>::iterator tmp_iter;
	if (mem_map.empty())
	{
		if (check_poison(heap_address, size)) { return heap_address; }
	}
	if ((char*)(mem_map.begin()->first) - (char*)(heap_address) >= size)
	{
		if (check_poison(heap_address, size)) { return heap_address; }
	}
	for (iter = mem_map.begin(); iter != mem_map.end(); iter++)
	{
		tmp_iter = iter;
		if (++tmp_iter != mem_map.end())
		{
			if ((char*)(tmp_iter->first) - ((char*)(iter->first) + ((iter->second.size - 1 + block_size) / block_size) * block_size) >= size)
			{
				void* ptr = (void*)((char*)(iter->first) + ((iter->second.size - 1 + block_size) / block_size) * block_size);
				if (check_poison(ptr, size)) { return ptr; }
			}
		} else {
			if ((char*)(iter->first) + ((iter->second.size - 1 + block_size) / block_size) * block_size + size <= end_of_heap)
			{
				void* ptr = (void*)((char*)(iter->first) + ((iter->second.size - 1 + block_size) / block_size) * block_size);
				if (check_poison(ptr, size)) { return ptr; }
			}
		}
	}
	return NULL;
}

heap_ludmila::~heap_ludmila() 
{ 
	if( alloc_sz ) 
	{
		Err("[heap] destruct not empty %p\n", alloc_sz );
		this->statistics();
	} else {
		if (heap_address != NULL)
		{
			std::free(heap_address);
		}
	}
}

void* heap_ludmila::alloc( size_t sz, unsigned int tag )
{ 
	if (!(this->flag & heap876::alloc_tagged)) { tag = 0; }
	unsigned int size = (sz - 1 + block_size) / block_size;
	WaitForSingleObject(mutex, INFINITE);
	if( ( alloc_sz + sz ) > total_limit )
	{
		Err("[heap] failed to alloc {sz=%p, tg=0x%x} sz=%p, total=%p\n",
			sz, tag, alloc_sz, total_limit );
		this->statistics();
		ReleaseMutex(mutex);
		return NULL;
	}
	void* ptr = find_block(size * block_size);
	if (ptr != NULL)
	{
		mem_block mb = {sz, tag};
		mem_map.insert(std::make_pair(ptr, mb));
		if (this->flag & heap876::alloc_debug)
		{
			memset(ptr, POISON_ALLOC, sz);
		}
		alloc_sz += sz;
		ReleaseMutex(mutex);
		return ptr;
	} else {
		Err("[heap] failed to alloc because of the fragmentation of memory {sz=%p, tg=0x%x} sz=%p, total=%p\n",
			sz, tag, alloc_sz, total_limit );
		this->statistics();
		ReleaseMutex(mutex);
		return NULL;
	}
}

void heap_ludmila::free_base(void *ptr, map<void*, mem_block>::iterator iter)
{
	size_t sz = iter->second.size;
	mem_map.erase(iter);
	if (this->flag & heap876::alloc_debug)
	{
		memset(ptr, POISON_FREE, sz);
	}
	alloc_sz -= sz;
}

void heap_ludmila::free(void *ptr)
{
	WaitForSingleObject(mutex, INFINITE);
	map<void*, mem_block>::iterator iter = mem_map.find(ptr);
	if (iter != mem_map.end())
	{
		free_base(ptr, iter); 
	} else {
		Err("Can't free piece of memory, it wasn't allocated or the pointer is wrong\n");
	}
	ReleaseMutex(mutex);
}

void heap_ludmila::free_all(unsigned int tag)
{
	if (this->flag & heap876::alloc_tagged)
	{
		map<void*, mem_block>::iterator iter;
		WaitForSingleObject(mutex, INFINITE);
		for (iter = mem_map.begin(); iter != mem_map.end(); )
		{
			if (iter->second.tag == tag)
			{
				void *ptr = iter->first;
				map<void*, mem_block>::iterator tmp_iter;
				tmp_iter = iter;
				iter++;
				free_base(ptr, tmp_iter);
			} else {
				iter++;
			}
		}
		ReleaseMutex(mutex);
	} else {
		Err("Memory allocation with tags is disabled\n");
	}
}